package com.fwpsl.graph;

import java.util.*;

/**
 * @author: 风戏fw
 * @date: 2024/4/12
 * @description: 拓扑排序是一种对有向无环图（DAG）进行排序的算法，它将所有顶点排成一个线性序列，使得对于任意一条有向边（u, v），
 * u在序列中都出现在v之前。拓扑排序的思想：按照任务的先后顺序制定一个任务列表，每个任务都依赖于前面的任务完成后才能开始。
 */
public class TopologicalOrder {

    /**
     * 拓扑排序函数 - 卡恩算法
     * <p>
     * 卡恩算法（Kahn's algorithm）是一种拓扑排序算法，用于有向无环图（DAG, Directed Acyclic Graph）的顶点排序。
     * 拓扑排序是对DAG的顶点进行线性排序，使得对每一条有向边 (u, v)，均有 u（在排序记录中）比 v 先出现。
     *
     * @param graph
     * @param <T>
     * @return
     */
    public static <T> List<Vertex<T>> kahnOrder(Graph<T> graph) {
        List<Vertex<T>> list = new ArrayList<>();
        if (graph.getVertexNum() <= 0) {
            return list;
        }

        // 每个顶点的入度值
        HashMap<Vertex<T>, Integer> inDegreMap = graph.getInDegreMap();

        // 将入度为0的顶点加入队列
        Queue<Vertex<T>> queue = new LinkedList<>();
        for (Vertex<T> vertex : graph.getVertices()) {
            if (inDegreMap.get(vertex) == 0) {
                queue.offer(vertex);
            }
        }

        // 拓扑排序，每次将入度为0的顶点取出来放入结果集中，并将该顶点的后继顶点入度值-1
        while (!queue.isEmpty()) {
            Vertex<T> vertex = queue.poll();
            list.add(vertex);
            for (Edge<T> edge : vertex.getEdges()) {
                Integer degree = inDegreMap.get(edge.getDestination()) - 1;
                inDegreMap.put(edge.getDestination(), degree);
                if (degree == 0) {
                    queue.offer(edge.getDestination());
                }
            }
        }

        // 检查是否所有顶点都被访问。未全部访问，说明有环。
        if (list.size() != graph.getVertexNum()) {
            return new ArrayList<>();
        }

        return list;
    }

    /**
     * 拓扑排序函数 - 采用DFS计算
     * <p>
     * 使用深度优先搜索（DFS）来计算拓扑排序是另一种常见的方法。基本思路是，从任意一个没有前驱（即入度为0）的顶点开始深度优先搜索，
     * 在搜索过程中删除访问过的顶点及其出边，最终得到的顶点序列即为拓扑排序。
     *
     * @param graph
     * @param <T>
     * @return
     */
    public static <T> List<Vertex<T>> dfsOrder(Graph<T> graph) {
        // 使用栈来存储拓扑排序的结果
        Deque<Vertex<T>> stack = new LinkedList<>();

        // 初始化访问数组
        Map<Vertex<T>, Boolean> visitedMap = new HashMap<>();
        for (Vertex<T> vertex : graph.getVertices()) {
            visitedMap.put(vertex, Boolean.FALSE);
        }

        for (Vertex<T> vertex : graph.getVertices()) {
            if (!visitedMap.get(vertex)) {
                dfs(vertex, visitedMap, stack);
            }
        }

        // 输出拓扑排序结果
        List<Vertex<T>> list = new ArrayList<>(stack.size());
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        return list;
    }

    /**
     * 深度优先搜索函数
     *
     * @param vertex
     * @param visitedMap
     * @param stack
     * @param <T>
     */
    private static <T> void dfs(Vertex<T> vertex, Map<Vertex<T>, Boolean> visitedMap, Deque<Vertex<T>> stack) {
        // 标记当前顶点为已访问
        visitedMap.put(vertex, Boolean.TRUE);

        // 遍历当前顶点的所有邻接顶点
        for (Edge<T> edge : vertex.getEdges()) {
            if (!visitedMap.get(edge.getDestination())) {
                dfs(edge.getDestination(), visitedMap, stack);
            }
        }

        // 将当前顶点压入栈中
        stack.push(vertex);
    }

    public static void main(String[] args) {
        Graph<Integer> graph = new Graph();

        graph.addEdge(2, 3);
        graph.addEdge(3, 1);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
        graph.addEdge(5, 0);
        graph.addEdge(5, 2);

        // 卡恩算法
        System.out.print("卡恩算法 - 拓扑排序结果：" + Graph.printVerties(kahnOrder(graph)));
        System.out.println();

        // 深度优先搜索（DFS）
        System.out.print("DFS - 拓扑排序结果：" + Graph.printVerties(dfsOrder(graph)));
        System.out.println();
    }
}
